1. Field of the Invention
The present invention relates generally to compression and decompression of digitized image data used, for example, to represent text, graphics and scanned images. More particularly, the invention relates to encoding variant color image data during compression of the image data.
2. State of the Art
Digitized images displayed on scanners, monitors and printers are typically quantized on a pixel-by-pixel basis and stored in memory as pixel maps, more commonly referred to as pixmaps. A pixmap is a two-dimensional array of picture elements mapped to locations of the digitized image.
To provide sufficient color range and fidelity, each pixel is typically stored in memory as a set of color coordinates which define the pixel's color location in a given color space. For example, a pixel is typically represented by its red, green and blue color component values, or by its cyan, magenta and yellow color component values. The fidelity of the color reproduction is a function of the accuracy with which each color component is represented.
Due to the increased volume of data required to represent color images, effort has been directed to compression of color data pixmaps. Because it is not practical or possible to provide a digital representation for all possible colors, the data used to represent each color component is necessarily compromised. Color fidelity is further compromised when the data used to represent the various colors of an image is compressed.
Early attempts at image compression relied upon techniques deemed suitable for non-scanned image data (such as text and synthetic graphics), assuming that they would work equally well for scanned images. One such technique was run-length coding, as described in "Inside Macintosh, Volumes I, II, III", Addison-Wesley, Reading, Mass., 1985, ISBN 0-201-17737-4. Run-length compression exploits the repetition of pixel values in long data "runs" by transmitting a single pixel value together with the length of the "run". Such techniques are relatively simple and effective for data used to represent text and line-art. However, run-length coding techniques have proven less suitable for scanned images (such as scanned photographs or video images) where numerous colors typically exist.
More advanced compression techniques are directed to maintaining color as close to full fidelity as possible. However, these techniques are theoretically "lossy" in that information content (such as edge acuity of text included in the image) is not maintained.
For example, "Data Compression--Techniques and Applications", Van Nostrand, Reinhold, N.Y. 1985, ISBN 0-534-03418, describes the use of transform-based compression techniques for image data. These techniques, such as the Hadamard Transform, the Fourier Transform and the Principal Component Transform (also known as the Karhunen-Loeve Transform), transform one- or two- dimensional data into a space having more desirable properties. One such property is an ability to easily distinguish which data points can be encoded with less precision, or even dropped, without noticeably degrading the image perceived by the unaided eye when an inverse transform is applied to the lossy representation.
The Hadamard Transform transforms an input space into one which is spanned by the Walsh-Rademacher functions. The Fourier Transform transforms the input space into one which is spanned by complex exponentials. The Principal Component Transform transforms the input space into one which is spanned by the eigenvectors associated with the input data. Although the Principal Component Transform is preferred, the amount of computation required to perform compression is practically prohibitive.
More recently, the Discrete Cosine Transform was developed to avoid the prohibitive computation of the Principal Component Transform. The basis functions of the Discrete Cosine Transform are cosines of various frequencies. For photographic images, this transform has been determined to yield results closer to that of the Principal Component Transform than any transform other than the Principal Component Transform itself. The Discrete Cosine Transform, in combination with entropy-preserving compression techniques, evolved into the industry standard (Joint Photographic Experts Group) JPEG compression, as described in "Graphics File Formats", Windcrest/McGraw-Hill, Blue Ridge Summit, Pa., 1992, ISBN 0-8306-3059-7.
With the exception of the Hadamard Transform and a few others, the basis functions of the transforms used for image compression tend to be smooth functions. This is the case with the complex exponentials of the Fourier Transform and the cosine functions of the Discrete Cosine Transform. Therefore, these transforms do not yield good compression ratios when sharp edges are to be represented without perceptible degradation. Although these transforms are suited to representing scanned images, they are far from ideal for representing text and synthetic graphics.
Known efforts for compressing image data have addressed this drawback of compression transforms by segregating the data of a pixmap into two components: (1) scanned image components and (2) all remaining components (such as text and synthetic graphics). Once segregated, the scanned image components are passed through compression techniques better suited for compressing scanned images (such as the JPEG industry standard compression techniques). The remaining components of the image data are separately passed to compression techniques better suited for objects that require good edge acuity (such as run length encoding).
However, this technique of segregating image data components suffers significant drawbacks. One such drawback is that the function of segregating presents problems. Objects included within the image data have to be tagged as scanned image data or as non-scanned image data before being placed into the pixmap. Otherwise, there is no way of determining the type of object to which a pixel belongs. Additional complexities result when overlapping areas of scanned images and non-scanned images are included within the image data.
Accordingly, it would be desirable to provide a technique for compressing image data without requiring the complexities associated with segregating the image data into its scanned and non-scanned components. It would further be desirable to reduce any perceptible degradation of the decompressed image, regardless of whether the image data includes scanned images, non-scanned images or any combination thereof. Further, it would be desirable to achieve such features using reduced amounts of memory storage, and using techniques suitable for real-time compression of an incoming data stream.